/*
 * Support for parse trees for the compiler.
 *
 * Added by Beek (Tim Hollebeek) 9/29/94.  Only converting expression parsing
 *    to parse trees at this point; the rest of code generation will likely
 *    follow later.
 *
 * Note: it did.  See ChangeLogs.
 *
 */

#include <stdlib.h>
#include "macros.h"
#include "opcodes.h"
#include "compiler.h"
#include "simulate.h" // for strput, EndOf
#include "trees.h"

#define NODES_PER_BLOCK         256

typedef struct parse_node_block_s {
	struct parse_node_block_s *next;
	parse_node_t nodes[NODES_PER_BLOCK];
} parse_node_block_t;

/* our globals */
static parse_node_block_t *parse_block_list = 0;
static parse_node_block_t *free_block_list = 0;

static parse_node_t *next_node = 0;
static parse_node_t *last_node = 0;

/* called by code generation when it is done with the tree */
void free_tree()
{
	parse_node_block_t *cur_block;

	if (!(cur_block = parse_block_list))
		return;

	while (cur_block->next) cur_block = cur_block->next;

	/* put all the blocks in the free list */
	cur_block->next = free_block_list;
	free_block_list = parse_block_list;
	parse_block_list = 0;
	next_node = 0;
	last_node = 0;
}

/* called when the parser cleans up */
void release_tree()
{
	parse_node_block_t *cur_block;
	parse_node_block_t *next_block;

	free_tree();
	next_block = free_block_list;
	while ((cur_block = next_block)) {
		next_block = cur_block->next;
		free(cur_block);
	}
	free_block_list = 0;
}

/* get a new node to add to the tree */
parse_node_t * new_node()
{
	parse_node_block_t *cur_block;

	/* fast case */
	if (next_node < last_node) {
		next_node->line = current_line;
		return next_node++;
	}

	/* no more nodes in the current block; do we have a free one? */
	if ((cur_block = free_block_list)) {
		free_block_list = cur_block->next;
	} else {
		cur_block = ALLOCATE(parse_node_block_t);
	}
	/* add to block list */
	cur_block->next = parse_block_list;
	parse_block_list = cur_block;
	/* point the nodes correctly */
	next_node = &cur_block->nodes[0];
	last_node = &cur_block->nodes[NODES_PER_BLOCK];
	next_node->line = current_line;
	return next_node++;
}

/* get a new node to add to the tree, but don't count it for line # purposes
 * This should be used for nodes that hold expressions together but don't
 * generate any code themselves (NODE_IF, etc)
 */
parse_node_t * new_node_no_line()
{
	parse_node_block_t *cur_block;

	/* fast case */
	if (next_node < last_node) {
		next_node->line = 0;
		return next_node++;
	}
	/* no more nodes in the current block; do we have a free one? */
	if ((cur_block = free_block_list)) {
		free_block_list = cur_block->next;
	} else {
		cur_block = ALLOCATE(parse_node_block_t);
	}
	/* add to block list */
	cur_block->next = parse_block_list;
	parse_block_list = cur_block;
	/* point the nodes correctly */
	next_node = &cur_block->nodes[0];
	last_node = &cur_block->nodes[NODES_PER_BLOCK];
	next_node->line = 0;
	return next_node++;
}

/* create an optimized typical binary integer operator */
parse_node_t * binary_int_op(parse_node_t *l, parse_node_t *r,
		char op, char *name)
{
	parse_node_t *ret;

	if (!IS_TYPE(l->type, TYPE_NUMBER)) {
		char buf[256];
		char *end = EndOf(buf);
		char *p;

		p = strput(buf, end, "Bad left argument to '");
		p = strput(p, end, name);
		p = strput(p, end, "' : \"");
		p = get_type_name(p, end, l->type);
		p = strput(p, end, "\"");
		yyerror(buf);
	}
	if (!IS_TYPE(r->type, TYPE_NUMBER)) {
		char buf[256];
		char *end = EndOf(buf);
		char *p;

		p = strput(buf, end, "Bad right argument to '");
		p = strput(p, end, name);
		p = strput(p, end, "' : \"");
		p = get_type_name(p, end, r->type);
		p = strput(p, end, "\"");
		yyerror(buf);
	}
	if (l->kind == NODE_NUMBER) {
		if (r->kind == NODE_NUMBER) {
			switch (op) {
				case F_MOD:
					    if (r->v.number == 0) {
						    yyerror("Modulo by zero constant");
						    break;
					    }
					    l->v.number %= r->v.number; break;
				default: fatal("Unknown opcode in binary_int_op()\n");
			}
			return l;
		}
	}
	CREATE_BINARY_OP(ret, op, TYPE_NUMBER, l, r);
	return ret;
}

static parse_node_t * throw_away_call(parse_node_t *pn)
{
    parse_node_t *enode;
    parse_node_t *ret = 0;
    parse_node_t *arg;

    enode = pn->r.expr;
    while (enode) {
	arg = insert_pop_value(enode->v.expr);
	if (arg) {
	    /* woops.  Don't lose the side effect. */
	    if (ret) {
		parse_node_t *tmp;
		CREATE_STATEMENTS(tmp, ret, arg);
		ret = tmp;
	    } else {
		ret = arg;
	    }
	}
	enode = enode->r.expr;
    }
    return ret;
}

static parse_node_t * throw_away_mapping(parse_node_t *pn)
{
    parse_node_t *enode;
    parse_node_t *ret = 0;
    parse_node_t *arg;

    enode = pn->r.expr;
    while (enode) {
	arg = insert_pop_value(enode->v.expr->l.expr);
	if (arg) {
	    /* woops.  Don't lose the side effect. */
	    if (ret) {
		parse_node_t *tmp;
		CREATE_STATEMENTS(tmp, ret, arg);
		ret = tmp;
	    } else {
		ret = arg;
	    }
	}
	arg = insert_pop_value(enode->v.expr->r.expr);
	if (arg) {
	    /* woops.  Don't lose the side effect. */
	    if (ret) {
		parse_node_t *tmp;
		CREATE_STATEMENTS(tmp, ret, arg);
		ret = tmp;
	    } else {
		ret = arg;
	    }
	}
	enode = enode->r.expr;
    }
    return ret;
}

parse_node_t *insert_pop_value(parse_node_t *expr)
{
	parse_node_t *replacement;

	if (!expr)
		return 0;
	if (expr->type == TYPE_NOVALUE) {
		expr->type = TYPE_VOID;
		return expr;
	}
	switch (expr->kind) {
		case NODE_EFUN:
			if (expr->v.number & NOVALUE_USED_FLAG) {
				expr->v.number &= ~NOVALUE_USED_FLAG;
				return expr;
			}
			break;
		case NODE_TWO_VALUES:
			/* (two-values expr1 expr2) where expr1 is already popped.
			 *
			 * instead of: (pop (two-values expr1 expr2))
			 * generated:  (two-values expr (pop expr2))
			 *
			 * both of which generate the same code, but the second optimizes
			 * better in cases like: i++, j++
			 *
			 * we get: (two-values (inc i) (post-inc j))
			 * first: (pop (two-values (inc i) (post-inc j)))
			 * -> INC i; POST_INC j; POP
			 * second: (two-values (inc i) (inc j))
			 * -> INC i; INC j
			 */
			if ((expr->r.expr = insert_pop_value(expr->r.expr)))
				return expr;
			return expr->l.expr;
		case NODE_IF:
			/* a NODE_IF that gets popped is a (x ? y : z);
			 * propagate the pop in order to produce the same code as
			 * if (x) y; else z;
			 */
			expr->l.expr = insert_pop_value(expr->l.expr);
			expr->r.expr = insert_pop_value(expr->r.expr);

			if (!expr->l.expr && !expr->r.expr) {
				/* if both branches do nothing, don't bother with the test ... */
				return insert_pop_value(expr->v.expr);
			}
			return expr;
		case NODE_CALL:
		case NODE_BINARY_OP:
		case NODE_UNARY_OP_1:
		case NODE_UNARY_OP:
		case NODE_OPCODE_1:
			switch (expr->v.number) {
				case F_AGGREGATE_ASSOC:
					/* This has to be done specially b/c of the way mapping constants
					   are stored */
					return throw_away_mapping(expr);
				case F_AGGREGATE:
					return throw_away_call(expr);
				case F_NOT: case F_NEGATE:
					expr = insert_pop_value(expr->r.expr);
					return expr;
				case F_LOCAL: case F_GLOBAL:
					return 0;
				case F_EQ: case F_NE: case F_GT: case F_GE: case F_LT: case F_LE:
				case F_ADD: case F_SUBTRACT: case F_MULTIPLY: case F_DIVIDE:
				case F_MOD:
				case F_INDEX:
					if ((expr->l.expr = insert_pop_value(expr->l.expr))) {
						if ((expr->r.expr = insert_pop_value(expr->r.expr))) {
							expr->kind = NODE_TWO_VALUES;
							return expr;
						} else
							return expr->l.expr;
					} else
						return insert_pop_value(expr->r.expr);
					break;
				case F_ASSIGN:
					if (IS_NODE(expr->r.expr, NODE_OPCODE_1, F_LOCAL_LVALUE)) {
						int tmp = expr->r.expr->l.number;
						expr->kind = NODE_UNARY_OP_1;
						expr->r.expr = expr->l.expr;
						expr->v.number = F_VOID_ASSIGN_LOCAL;
						expr->l.number = tmp;
					} else expr->v.number = F_VOID_ASSIGN;
					return expr;
			}
			break;
		case NODE_NUMBER:
		case NODE_STRING:
		case NODE_REAL:
			return 0;
	}
	CREATE_UNARY_OP(replacement, F_POP_VALUE, 0, expr);
	return replacement;
}

parse_node_t *pop_value(parse_node_t *pn)
{
	if (pn) {
		parse_node_t *ret = insert_pop_value(pn);

		if (!ret) {
			if (pn->kind == NODE_BINARY_OP && pn->v.number >= F_EQ &&
					pn->v.number <= F_GT)
				yywarn("Value of conditional expression is unused");
			else
				yywarn("Expression has no side effects, and the value is unused");
		}
		return ret;
	}

	return 0;
}

parse_node_t *optimize_loop_test(parse_node_t *pn)
{
	parse_node_t *ret;

	if (!pn) return 0;

	if (IS_NODE(pn, NODE_BINARY_OP, F_LT) &&
			IS_NODE(pn->l.expr, NODE_OPCODE_1, F_LOCAL)) {
		if (IS_NODE(pn->r.expr, NODE_OPCODE_1, F_LOCAL)) {
			CREATE_OPCODE_2(ret, F_LOOP_COND_LOCAL, 0,
					pn->l.expr->l.number,
					pn->r.expr->l.number);
		} else if (pn->r.expr->kind == NODE_NUMBER) {
			CREATE_OPCODE_2(ret, F_LOOP_COND_NUMBER, 0,
					pn->l.expr->l.number,
					pn->r.expr->v.number);
		} else
			ret = pn;
	} else
		ret = pn;

	return ret;
}

int is_boolean(parse_node_t *pn)
{
	switch (pn->kind) {
		case NODE_UNARY_OP:
			if (pn->v.number == F_NOT)
				return 1;
			return 0;
		case NODE_BINARY_OP:
			if (pn->v.number >= F_EQ && pn->v.number <= F_GT)
				return 1;
			return 0;
		case NODE_LAND_LOR:
		case NODE_BRANCH_LINK:
			return 1;
	}
	return 0;
}
